

//next为后继
//prev为前驱


class MyNode{
    public int data;
    public MyNode next;
    public MyNode prev;
    public MyNode (int data){
        this.data=data;
    }
}

public class MyLinkedilist{
    public  MyNode head; 
    public  MyNode tail;
    public void addFirst(int data){
        MyNode node=new  MyNode(data);
        if(this.head==null){
            this.head=node;
            this.tail=node;
            return;
        }
        node.next=this.head;    
        this.head.prev=node;
        this.head=node;
    }
    public void display(){
        if(this.head==null){
            return;
        }
        MyNode tap=this.head;
        while(tap!=null){
            System.out.println(tap.data);
            tap=tap.next;
        }
    }
    public void addLast(int data){
        MyNode node = new MyNode(data);
        if(this.head==null){
            this.head=node;
            this.tail=node;
        }
        this.tail.next=node;
        node.prev=tail;
        this.tail=node;
    }
    public boolean contains(int key){
        MyNode tap=this.head;
        while(tap!=null){
            if(tap.data==key){
                return true;
            }
            tap=tap.next;
        }
        return false;
    }
    public int size(){
        int i=0;
        MyNode tap=this.head;
        while(tap!=null){
            tap=tap.next;
            i++;
        }
        return i;
    }
    public void checkIndex(int index){
        if(index<0||index>size()){
            throw new RuntimeException("index不合法");
        }
    }

    public MyNode searchIndex(int index){
        MyNode cur=this.head;
        for(int i=0;i<=index;i++){
            cur=cur.next;
        }
        return cur;
    }
    public void addIndex(int index,int data){
        if(this.head==null){
            addFirst(data);
            return ;
        }
        checkIndex(index);
        if(index==size()){
            addLast(data);
            return ;
        }
        MyNode cur=searchIndex(index);
        MyNode node=new MyNode(data);
        node.next=cur;
        node.prev=cur.prev;
        cur=cur.prev;
        cur.next=node;
    }
    public int  remove(int key){
        MyNode cur=this.head;
        while(cur!=null){
            if(cur.data==key){
                if(cur==this.head){
                    this.head=this.head.next;
                    this.head.prev=null;
                }
                if(cur==tail){
                    tail=tail.prev;
                    tail.next=null;
                }
                cur.next.prev=cur.prev;
                cur.prev.next=cur.next;
                int oldData=cur.data;
                return oldData;
            }
            cur=cur.next;
        }
        return -1;
    }
    public void clear(){
        while(this.head!=null){
        MyNode cur=this.head.next;
            this.head.prev=null;
            this.head.next=null;
            this.head=cur;
        }
        this.tail=this.head;
    }
}